In multi-processor computer systems, tasks between the processors can be divided between the available processors and network resources. Shared address memory systems let the processors access common system memory. Local cache memory can also provide fast access to data for local processing tasks. The cache typically keeps copies of data from memory local to a number of other processor nodes.
As multi-processor systems get larger, the number of transaction requests from requesting agents to servicing agents also increases, and the system can become congested with message and data traffic. Larger systems can also suffer from request starvation when the length of time for servicing the transaction requests grows too long. There can also be problems with servicing requests “fairly” so as to optimize system performance.
A request priority system can assign priorities to transaction requests. This may also include a mechanism to deal with excessive negative acknowledgements (NACKs) from the servicing agents indicating that specific transaction requests cannot yet be serviced. In response to a NACK, a requesting agent may re-transmit another request for the service. The request priority may be a step function based on the number of NACKs received.
Such systems can tend to produce an excessive number of NACKed requests, which result in requests being re-injected back into the system. And previous such schemes did not ultimately guarantee starvation avoidance because conditions could arise where many contending requests have a saturated priority and thus all fairness of service ordering between them is lost. In addition, there was no persistence of fairness related state at the servicing agent between successive servicing actions—the service level was reset at the beginning of each servicing action and a new service level was determined to be the highest priority of any request rejected while that servicing action was under way—the target cache line was busy. Further, prior systems did not have nor need provisions for ensuring the forward progress of probe actions (required for managing system-wide data coherency) which contend for access to the processor domain or to intermediate shared resources (proxy agents). Nor did they deal with congestion related issues. Prior schemes had yet another problem—they relied on retry counts for determining request priority. This policy tended to promote more rapid accumulation of priority for requests originating from nearby requesting agents and was thus not an objective means of determining relative priority between contending requests.